'''
https://leetcode.cn/problems/maximum-length-of-pair-chain/
'''
import bisect
from typing import List


class Solution:
    # 最长递增子序列,修改了ends数组存放的东西
    def findLongestChain(self, pairs: List[List[int]]) -> int:
        n = len(pairs)
        pairs.sort()
        ends = []
        for i in range(0, n):
            # bisect_left： >= nums的最左位置
            # bisect_right: > nums的最s左位置
            k = bisect.bisect_left(ends, pairs[i][0])
            if k == len(ends):
                ends.append(pairs[i][1])
            else:
                if pairs[i][1] < ends[k]:
                    ends[k] = pairs[i][1]
        return len(ends)

    # 贪心
    def findLongestChain2(self, pairs: List[List[int]]) -> int:
        n = len(pairs)
        pairs.sort(key=lambda x: x[1])
        res, limit = 1, pairs[0][1]
        for i in range(1, n):
            if pairs[i][0] > limit:
                res += 1
                limit = pairs[i][1]
        return res


pairs = [[1,2],[2,3],[3,4]]
print(Solution().findLongestChain(pairs))